package leetcode.list;

import utils.node.ListNode;

/**
 * @Description: https://leetcode.cn/problems/merge-two-sorted-lists/
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 2
 * @Author Ammar
 * @Create 2023/5/3 06:19
 */
public class _21_合并两个有序链表 {

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 如果左链表为空
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        ListNode li = list1; // 要比较的左节点
        ListNode ri = list2; // 要比较的右节点
        ListNode listRoot = list2; // 合成链表的root
        ListNode listIndex = null; // 指向合成链表中的刚插入的节点

        // 第一次比较
        if (li.val < ri.val) {
            ListNode node = li; // 胜出node
            li = li.next;
            node.next = listRoot;
            listRoot = node;
            listIndex = node;
        } else {
            ri = ri.next;
            listIndex = listRoot;
        }

        while (li != null && ri != null) {
            if (li.val < ri.val) {
                ListNode node = li;
                li = li.next;
                // 将左链表的 node 节点插入 listIndex 的 next
                node.next = listIndex.next;
                listIndex.next = node;
            } else {
                ri = ri.next;
            }
            listIndex = listIndex.next;
        }
        // 左链表没有元素了也不用做任何操作
        // 右链表没有元素了
        if (ri == null) {
            // 将左链表的所有元素移动到listIndex.next
            listIndex.next = li;
        }
        return listRoot;
    }
}
